/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/13
 * \* Time: 20:36
 * \* To change this template use File | Settings | File Templates.
 * \* Description:有一个长度为arrLen的数组，开始有一个指针在索引0 处。
 *
 * 每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
 *
 * 给你两个整数steps 和arrLen ，请你计算并返回：在恰好执行steps次操作以后，指针仍然指向索引0 处的方案数。
 *
 * 由于答案可能会很大，请返回方案数 模10^9 + 7 后的结果。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * \
 */
public class 停在原地的方案数 {
    int mod = (int)1e9+7;
    public int numWays(int steps, int arrLen) {
        //最远到达的位置为 step / 2step/2（再远就回不来了）。
        int max=Math.min(steps/2,arrLen-1);
        //最终状态是f[0][0]
        //定义 f[i][j]代表当前剩余操作数为 i，所在位置为 j的所有方案数。
        //利用 f[i][x]依赖于 f[i + 1][y]，使用「滚动数组」方式进行优化空间即可。
        int[][] f=new int[2][arrLen+1];
        f[steps&1][0]=1;
        for(int i=steps-1;i>=0;i--){
            //减枝
            int edge = Math.min(i, max);
            int a = i & 1, b = (i + 1) & 1;
            for(int j=0;j<=edge;j++){
                f[a][j] = 0;
                //原地不动
                f[a][j]=(f[a][j]+f[b][j])%mod;
                //向右移动
                if (j - 1 >= 0) {
                    f[a][j] = (f[a][j] + f[b][j - 1]) % mod;
                }
                //向左移动
                if (j + 1 <= max) {
                    f[a][j] = (f[a][j] + f[b][j + 1]) % mod;
                }

            }
        }
        return f[0][0];
    }
}